package slidingwindow

import "container/list"

// 剑指 Offer 59 - I. 滑动窗口的最大值
// 给定一个数组 nums 和滑动窗口的大小 k，请找出所有滑动窗口里的最大值。
//
// 示例:
//
// 输入: nums = [1,3,-1,-3,5,3,6,7], 和 k = 3
// 输出: [3,3,5,5,6,7]
// 解释:

func GetMaxNumInWindow(arr []int, width int) []int {
	if len(arr) < width {return []int{}}

	ans := make([]int, len(arr)-width+1)
	monotStack := list.New()
	var index int
	for R:=0; R<len(arr); R++ {
		// 放入值的规则，遇到小的需要先弹出，直到大数停止，放在该位置后面
		for monotStack.Len() > 0 && arr[monotStack.Back().Value.(int)] < arr[R] {
			monotStack.Remove(monotStack.Back())
		}
		monotStack.PushBack(R)

		// 没有形成窗口之前，不弹出
		oldestIndex := monotStack.Front().Value.(int)
		if oldestIndex == R - width {
			monotStack.Remove(monotStack.Front())
		}

		// 形成窗口后添加结果
		if R >= width-1 {
			bigIndex := monotStack.Front().Value.(int)
			ans[index] = arr[bigIndex]
			index++
		}
	}
	return ans
}